package com.daji.search_and_sort;

import java.util.ArrayList;
import java.util.List;

/*
    基本思想：
        先比较个位，对个位进行一次排序（这样个位数的就会有序）；
        再比较十位，对十位进行一次排序（十位数的就会有序）；
        再比较百位，对百位进行一次排序（百位数的就会有序）；
        以此类推。
    如果一个数高位没有对应的位数，就当成0处理。比如处理十位时，数字6将被看做"06"
*/
public class RadixSort {
    public static void main(String[] args) {
        //本程序没有考虑负数的情况。
        int[] arr = {170, 45, 1, 75, 90, 802, 24, 2, 66, 98};
        int arrLen = arr.length;
        radixsort(arr, arrLen);
        print(arr, arrLen);
    }

    private static void radixsort(int[] arr, int arrLen) {

        //求最大数（是为了得到最大数的位数。也就是最大数有几位数字）
        int arrMax = getMax(arr, arrLen);

        //exp就是个位，十位，百位等等以此类推。
        //先从最低位取，每次迭代取高一位。
        //每迭代一次，对应的位就会有序。比如迭代第一次结束后，整个数组按个位有序排列，迭代第二次结束后，
        //十位数就会有序。以此类推。其实就是单独计数排序个位，计数排序十位，计数排序百位……以此类推
        for (int exp = 1; arrMax / exp > 0; exp *= 10) {
            countSort(arr, arrLen, exp);
        }
    }

    //exp就是个位，十位，百位等等以此类推。
    private static void countSort(int[] arr, int arrLen, int exp) {
        List<List<Integer>> buckets = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
            //每个桶里面又有存储空间
            ArrayList<Integer> bucket = new ArrayList<>();
            buckets.add(bucket);
        }

        //向桶中相同数码(数位)的位置塞元素
        for (int i = 0; i < arrLen; i++) {
            //digit为取得某个数中间的某位数码(数位)。
            // 例：当arr[i]为234，exp为10(十位)，此时digit就是3
            //例2：当arr[i]为234，exp为1 (个位)，此时digit就是4
            int digit = (arr[i] / exp) % 10;
            buckets.get(digit).add(arr[i]);
        }

        //将每个桶中元素聚合，得到排好序的数组
        //concat -> concatenate v.使连锁，联结
        /* concatenate buckets to origin array */
        int index = 0;
        for (List<Integer> bucket : buckets) {
            for (int value : bucket) {
                arr[index++] = value;

            }
        }
    }

    private static int getMax(int[] arr, int arrLen) {
        int arrMax = arr[0];
        for (int i = 1; i < arrLen; i++) {
            if (arr[i] > arrMax) {
                arrMax = arr[i];
            }
        }
        return arrMax;
    }

    static void print(int[] arr, int arrLen) {
        for (int i = 0; i < arrLen; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}